package main.leetcode.offer.secondround.from03to50;

/** 42.连续子数组的最大和 */
public class ex42 {
    //    public int maxSubArray(int[] nums) {
    //        if (nums == null || nums.length == 0) {
    //            return 0;
    //        }
    //        // dp[i]代表以nums[i]结尾的连续子数组的最大和
    //        int res = nums[0];
    //        int[] dp = new int[nums.length + 1];
    //        dp[0] = nums[0];
    //        for (int i = 1; i < nums.length; ++i) {
    //            // 单独成为一段还是加入 dp(i - 1) 对应的那一段
    //            dp[i] = dp[i - 1] < 0 ? nums[i] : dp[i - 1] + nums[i];
    //            res = Math.max(res, dp[i]);
    //        }
    //        return res;
    //    }

    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 记录以nums[i-1]结尾的连续子数组的最大和
        int pre = 0;
        int res = nums[0];
        for (int num : nums) {
            // 比较是否应该将当前num加入该连续子数组
            pre = Math.max(pre + num, num);
            // 更新最大值
            res = Math.max(pre, res);
        }
        return res;
    }
}
